package org.czx.datactruct.six;

import org.czx.datactruct.fifth.StackInterface;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * @author czx
 * @date 2020/9/11 15:59
 */
public final class ArrayStack<T> implements StackInterface<T> {
    private T[] stack;

    private int topIndex;  //栈顶位置
    private boolean initialized = false;

    private static final int DEFAULT_CAPACITY = 50;
    private static final int MAX_CAPACITY = 10000;

    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayStack(int initialCapacity) {
        checkCapacity(initialCapacity);
        // The cast is safe because the new array contains null entries
        @SuppressWarnings("unchecked")
        T[] tempStack = (T[]) new Object[initialCapacity];
        stack = tempStack;
        topIndex = -1;
        initialized = true;
    }

    @Override
    public void push(T newEntry) {
        checkInitialization();
        ensureCapacity();
        stack[topIndex + 1] = newEntry;
        topIndex++;
    }

    @Override
    public T pop() {
        T pop = peek();
        stack[topIndex] = null;
        topIndex--;
        return pop;
    }

    @Override
    public T peek() {
        checkInitialization();
        if (isEmpty())
            throw new EmptyStackException();
        else
            return stack[topIndex];
    }

    @Override
    public boolean isEmpty() {
        return topIndex < 0;
    }

    @Override
    public void clear() {
        topIndex = -1;
    }

    private void checkInitialization() {
        if (!initialized)
            throw new SecurityException("ArrayStack object is corrupt.");
    }

    // Returns true if the array stack is full, or false if not.
    private void ensureCapacity() {
        if (topIndex >= stack.length - 1)
            doubleCapacity();
    }

    /**
     * 数组扩容两倍
     */
    private void doubleCapacity() {
        int newLength = 2 * stack.length;
        checkCapacity(newLength);
        stack = Arrays.copyOf(stack, newLength);
    }

    private void checkCapacity(int initialCapacity) {
        if (initialCapacity > MAX_CAPACITY)
            throw new IllegalStateException("Attempt to create a stack " +
                    "whose capacity exceeds " +
                    "allowed maximum of ." + MAX_CAPACITY);
    }
}
